/*
    bitmap
*/


#include "bitmap.h"



char* g_bitmap = NULL;
int g_size = 0;
int g_base = 0;

/*
    num 要记录的最大数值，big位的个数
    start 开始的位置
*/
int bitmap_init(int num, int start){
    int size = num / 8 + 1; //一个字节8位
    g_bitmap = (char*) malloc(size * sizeof(char));
    if(g_bitmap == NULL){
        return 0;
    }
    g_base = start;
    g_size = size;
    memset(g_bitmap, 0, g_size);
}

/*
    将对应的位设置为1
*/
int bitmap_set(int index){
    int quo = (index - g_base) / 8;
    int reminder = (index - g_base) % 8;
    unsigned char x = (0x1<<reminder);
    if( quo > g_size) {
        //分配的内存过小了
        printf("the malloc memory to small!");
        return 0;
    }
    g_bitmap[quo] = g_bitmap[quo] | x;
    return 1;
}

/*
    取bitmap指定位的值, >0 表示有数据
*/
int bitmap_get(int i){
    int quo = i / 8;
    int reminder = i % 8;
    unsigned char x = (0x1 << reminder);
    unsigned char res;
    if( quo > g_size){
        return -1;
    }
    res = g_bitmap[quo] & x;
    return res > 0 ? 1 : 0;
}

/*
    返回 index位对应的值
*/
int bitmap_data(int index){
    return index + g_base;
}

void bitmap_free(){
    free(g_bitmap);
    g_bitmap = NULL;
}





/*
   bitmap实现排序去重功能,对大数据很有用, max_num 是数组中最大的数
   get_bitmap(tb, max_num)
*/
int get_bitmap(lua_State *L)
{
    int max_num = luaL_checkinteger(L, -1); //max_num 数组中最大的数值
    lua_pop(L, 1);
    max_num = max_num + 1; //数据的位数，保存比数据中最大的数大1
    int len = luaL_len(L, -1); //取table的长度
    int a[max_num];
    for(int i=1; i <= len; i++){
        lua_rawgeti(L, -1, i); //把key=i的值 弹出到栈顶
        int num = luaL_checkinteger(L, -1); //取出栈顶value
        a[i-1] = num;
        lua_pop(L, 1); //弹出栈顶元素
    }

    bitmap_init(max_num, 0); //长度为max_num 的bitmap
    for(int i=0; i < len; i++){
        bitmap_set(a[i]);
    }
    lua_pop(L, lua_gettop(L));//清空栈

    //创建一个table
    lua_newtable(L);
    int key = 1;
    for(int i=0; i < max_num; i++){
        //返回到table中
        if(bitmap_get(i) > 0){
            lua_pushinteger(L, key++);
            int num = bitmap_data(i);
            lua_pushinteger(L, num);
            lua_settable(L, -3); //就是把表在lua堆栈中的值弹出来，index 是table 在堆栈中的位置，假如 table 在 -3, 则key 应该是 -2，value 是 -1

            /*
            这样也是tb[k]=num
                        int num = bitmap_data(i);
                        lua_pushinteger(L, num);
                        lua_rawseti(L, -2, key++); //设置tb[key] = num
            lua_settable 会触发元方法newindex， 但lua_rawset不会
            */
        }
    }
    bitmap_free();
    return 1;
}
